// @coding: utf8

#include <iostream>
#include <vector>
#include <random>

// @brief 二分搜索，找出值在数组中的位置
int bin_search(int* arr, int cnt, int target)
{
    int left = 0;
    int right = cnt - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target)
            return mid;
        else if (target < arr[mid])
            right = mid - 1;
        else // target > arr[mid]
            left = mid + 1;
    }
    return -1;
}

// @breif 找出值在数组中的位置，或者插入位置。 如果相等，则插入到第一个相等的值前面(常规做法，如果条件改为>=则可以实现放到最后一个相等值的后面)
int bin_insert_pos(int* arr, int cnt, int target)
{
    int left = 0;
    int right = cnt - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        //if (target == arr[mid])
        //    return mid;
        if (target > arr[mid])  // >=或者<=决定了相等情况下的搜索稳定性
            left = mid + 1;
        else // if (target > arr[mid])
            right = mid - 1;
    }
    return left;
}

int main()
{
    std::vector<int> vec;
    int cnt = 9;
    for (int idx = 0; idx < cnt; ++idx)
    {
        vec.push_back(idx);
    }

    for (int target = -2; target < cnt + 3; ++target)
    {
        int result = bin_search(vec.data(), vec.size(), target);
        std::cout << "tar=" << target << "," << "pos=" << result << std::endl;
    }

    std::cout << "bin_search_pos:" << std::endl;
    for (int target = -2; target < cnt + 3; ++target)
    {
        int result = bin_insert_pos(vec.data(), vec.size(), target);
        std::cout << "tar=" << target << "," << "pos=" << result << std::endl;
    }

    return 0;
}